package com.c2b.algorithm.leetcode.base;

/**
 * <a href="https://leetcode.cn/problems/reverse-nodes-in-even-length-groups/">反转偶数长度组的节点(Reverse Nodes in Even Length Groups)</a>
 * <p>给你一个链表的头节点 head 。</p>
 * <p>
 * 链表中的节点 按顺序 划分成若干 非空 组，这些非空组的长度构成一个自然数序列（1, 2, 3, 4, ...）。一个组的 长度 就是组中分配到的节点数目。换句话说：
 * <ui>
 * <li>节点 1 分配给第一组</li>
 * <li>节点 2 和 3 分配给第二组</li>
 * <li>节点 4、5 和 6 分配给第三组，以此类推</li>
 * </ui>
 * 注意，最后一组的长度可能小于或者等于 1 + 倒数第二组的长度 。
 * </p>
 * <p>反转 每个 偶数 长度组中的节点，并返回修改后链表的头节点 head 。</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：head = [5,2,6,3,9,1,7,3,8,4]
 *      输出：[5,6,2,3,9,1,4,8,3,7]
 *      解释：
 *          - 第一组长度为 1 ，奇数，没有发生反转。
 *          - 第二组长度为 2 ，偶数，节点反转。
 *          - 第三组长度为 3 ，奇数，没有发生反转。
 *          - 最后一组长度为 4 ，偶数，节点反转。
 *
 * 示例 2：
 *      输入：head = [1,1,0,6]
 *      输出：[1,0,1,6]
 *      解释：
 *          - 第一组长度为 1 ，没有发生反转。
 *          - 第二组长度为 2 ，节点反转。
 *          - 最后一组长度为 1 ，没有发生反转。
 *
 * 示例 3：
 *      输入：head = [2,1]
 *      输出：[2,1]
 *      解释：
 *          - 第一组长度为 1 ，没有发生反转。
 *          - 最后一组长度为 1 ，没有发生反转。
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 *  <ul>
 *      <li>链表中节点数目范围是 [1, 10^5]</li>
 *      <li>0 <= Node.val <= 10^5</li>
 *  </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/5/5 11:54
 */
public class LC2074ReverseNodesInEvenLengthGroups_M {

    static class Solution {
        public ListNode reverseEvenLengthGroups(ListNode head) {
            ListNode dummyHead = new ListNode(0, head);
            // 上一组的最后一个节点
            ListNode prevGroupLastNode = dummyHead;
            // 组号
            int groupNo = 1;
            while (prevGroupLastNode.next != null) {
                // 记录当前组的第一个节点，用于反转
                ListNode currGroupFirstNode = prevGroupLastNode.next;
                ListNode currNode = currGroupFirstNode;
                // 记录当前组节点的个数，最后一组节点的数量可能不等于groupNo
                int currGroupNodeSize = 1;
                for (int i = 1; i < groupNo && currNode.next != null; i++) {
                    currNode = currNode.next;
                    ++currGroupNodeSize;
                }
                // 偶数的 最低二进制位一定为 0；那么 (currGroupNodeSize & 1) == 1 成立，说明为偶数
                if ((currGroupNodeSize & 1) == 0) {
                    // 此时：currNode 位于当前组的最后一个节点
                    ListNode nextGroupHeadNode = currNode.next;
                    // 断开链表
                    currNode.next = null;
                    // 反转链表并拼接。反转后：currGroupFirstNode 变成当前组的最后一个节点
                    prevGroupLastNode.next = reserve(currGroupFirstNode);
                    currGroupFirstNode.next = nextGroupHeadNode;
                    // 进行下一次循环
                    prevGroupLastNode = currGroupFirstNode;
                } else {
                    // 进行下一次循环
                    prevGroupLastNode = currNode;
                }
                ++groupNo;
            }
            return dummyHead.next;
        }

        private ListNode reserve(ListNode head) {
            ListNode prevNode = null;
            ListNode currNode = head;
            ListNode nextNode;
            while (currNode != null) {
                nextNode = currNode.next;
                currNode.next = prevNode;
                prevNode = currNode;
                currNode = nextNode;
            }
            return prevNode;
        }
    }

    public static void main(String[] args) {
        //ListNode head = new ListNode(5);
        //head.next = new ListNode(2);
        //head.next.next = new ListNode(6);
        //head.next.next.next = new ListNode(3);
        //head.next.next.next.next = new ListNode(9);
        //head.next.next.next.next.next = new ListNode(1);
        //head.next.next.next.next.next.next = new ListNode(7);
        //head.next.next.next.next.next.next.next = new ListNode(3);
        //head.next.next.next.next.next.next.next.next = new ListNode(8);
        //head.next.next.next.next.next.next.next.next.next = new ListNode(4);
        ListNode head = new ListNode(1);
        head.next = new ListNode(1);
        head.next.next = new ListNode(0);
        head.next.next.next = new ListNode(6);
        //head.next.next.next.next = new ListNode(5);
        //head.next.next.next.next.next = new ListNode(3);
        //head.next.next.next.next.next.next = new ListNode(9);
        //head.next.next.next.next.next.next.next = new ListNode(7);
        Solution solution = new Solution();
        Printer.printListNode(solution.reverseEvenLengthGroups(head));
    }

}
